package LeetCode._04动态规划_;

import java.util.Arrays;

/*
    1.确定 base case
    2.确定「状态」，也就是原问题和子问题中会变化的变量
    3.确定「选择」，也就是导致「状态」产生变化的行为。
    4.明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，
    一般来说函数的参数就是状态转移中会变化的量，
    也就是上面说到的「状态」；
    函数的返回值就是题目要求我们计算的量。
    就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。
    dp 数组体现在数组索引：
 */
public class _322零钱兑换 {
    /*
        1.base case: amount = 0,return 0, amount < 0 return -1
        2.确定状态:目标金额就是状态,amount
        3.确定选择，每一种面值就是选择
        4.确定dp{i}:当目标金额为i时所需要的硬币个数

     */
    public int coinChange(int[] coins, int amount) {
        if(amount == 0) return 0;
        //dp(i):凑够i分时所需要的硬币
        int[] dp = new int[amount + 1];
        Arrays.fill(dp,amount+1); //对初始值进行操作,不然无法取得最小值
        dp[0] = 0;
        //所有状态中的所有选择
        for(int i=1;i<dp.length;++i){
            //每一个状态选择以后的最小值
            for(int coin : coins){
                //选择之后小于0，无解
                if(i - coin < 0) continue;
                dp[i] = Math.min(dp[i],dp[i-coin] + 1);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }
}
